import java.util.ArrayList;

/**
 * Created with Intellij IDEA.
 * Description;
 * User:TQ02
 * Data:2023-11-03
 * Time:19:25
 * Text：不同路径
 */
public class Text {
//不同路径二，0为遮挡物，1为可行路
    public int uniquePathsWithObstacles (ArrayList<ArrayList<Character>> obstacleGrid) {
        int n=obstacleGrid.size();
        int m=obstacleGrid.get(0).size();
        char[][] t1=new char[n][m];
        for(int i=0;i<n;i++)
        {
            for(int k=0;k<m;k++){
                t1[i][k]=obstacleGrid.get(i).get(k);
            }
        }
        int[][] t2=new int[n+1][m+1];
        t2[0][1]=1;
        for(int i=1;i<n+1;i++){
            for(int k=1;k<m+1;k++){
                if(t1[i-1][k-1]=='0'){
                    t2[i][k]=0;
                }else{
                    t2[i][k]=t2[i-1][k]+t2[i][k-1];
                }
            }
        }

        return t2[n][m];
    }
//    不同路径数一
    public int uniquePaths (int m, int n) {
        int[][] dp=new int[m][n];
        for (int i = 0; i < m; i++) {
            dp[i][0] = 1;
        }
        for (int i = 0; i < n; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < m; i++) {
            for (int k = 1; k < n; k++){
                dp[i][k]=dp[i-1][k]+dp[i][k-1];
            }
        }
        return dp[m-1][n-1];
    }
}
